# encoding=utf-8
'''
Created on Nov 21, 2012

@author: junior
'''
import sys
sys.path.append('search/modules/aima')
from search import Node

class GraphSearch(Node):

	def __init__(self, problem, frontier):
		self._problem = problem
		self._frontier = frontier

	def execute(self):
		"""Search through the successors of a problem to find a goal.
		The argument frontier should be an empty queue.
		If two paths reach a state, only use the first one. [Fig. 3.7]"""
		graph = []
		extendidos = 0
		self._frontier.append(Node(self._problem.initial))
		explored = set()
		tree_explored=set()

		while self._frontier:
			node = self._frontier.pop()
			if self._problem.goal_test(node.state):
				graph.append([node.state, []])
				return node, graph, extendidos
			explored.add(node.state)
			children = [child.state for child in node.expand(self._problem) if child.state not in explored and child not in self._frontier]
			self._frontier.extend(child for child in node.expand(self._problem) if child.state not in explored)
			graph.append([node.state, children])
		return None, graph, extendidos
